/*-------------------------------------------------------------------------
 *
 * sortsupport.h
 *	  加速排序的框架。
 *
 * 传统上，PostgreSQL 通过重复调用 SQL 可调用的比较函数 "cmp(x, y) returns int" 来实现排序，比较的值是需要比较的值对，其中比较函数是适当的 btree 索引操作类的 BTORDER_PROC pg_amproc 支持函数。
 *
 * 该文件定义了替代 API，允许以减少开销的方式进行排序。为了支持低开销排序，btree 操作类可以提供 BTSORTSUPPORT_PROC pg_amproc 条目，该条目必须接受一个内部类型的单个参数并返回 void。该参数实际上是指向 SortSupportData 结构的指针，该结构在下面定义。
 *
 * 如果提供了，BTSORTSUPPORT 函数将在排序设置期间被调用，它必须初始化提供的结构，指向可以调用以执行排序的函数。该 API 被定义为允许支持多种加速机制，但没有操作类要求提供所有机制。BTSORTSUPPORT 函数应简单地不为其不支持的机制设置任何函数指针。提供 BTSORTSUPPORT 而不提供比较器函数的操作类将自动由排序支持设置一个适配层。然而，支持可选的附加缩写键能力的操作类必须始终提供一个权威比较器，用于解决不明确的缩写比较并在中止缩写时使用。此外，还必须提供转换器和中止/成本计算函数。
 *
 * 所有排序支持函数在调用时都会传入 SortSupportData 结构的地址，以便它们可以用来存储所需的其他私有数据。特别地，对于支持排序的类型，在调用 BTSORTSUPPORT 之前，ssup_collation 字段被设置，并可以供所有支持函数使用。其他依赖于操作类的数据可以使用 ssup_extra 字段存储。此类数据应在 ssup_cxt 内存上下文中分配。
 *
 * 注意：由于 pg_amproc 函数是按 (lefttype, righttype) 索引的，因此可以将 BTSORTSUPPORT 函数与跨类型比较关联。这可以合理地用于为此类情况提供快速比较器函数，但可能不适用于任何其他加速方法。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/utils/sortsupport.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef SORTSUPPORT_H
#define SORTSUPPORT_H

#include "access/attnum.h"
#include "utils/relcache.h"

typedef struct SortSupportData *SortSupport;

typedef struct SortSupportData
{
	/*
	 * 这些字段在调用 BTSORTSUPPORT 函数之前被初始化，
	 * 之后不应更改。
	 */
	MemoryContext ssup_cxt;		/* 包含排序信息的上下文 */
	Oid			ssup_collation; /* 要使用的排序规则，或 InvalidOid */

	/*
	 * 额外的排序参数；但与 ssup_collation 不同，这些可以在调用
	 * BTSORTSUPPORT 后更改，因此在选择排序支持函数时
	 * 不要使用它们。
	 */
	bool		ssup_reverse;	/* 降序排序？ */
	bool		ssup_nulls_first;	/* 首先排序空值？ */

	/*
	 * 这些字段是调用者的工作区，不应被特定操作类的函数修改。
	 */
	AttrNumber	ssup_attno;		/* 要排序的列号 */

	/*
	 * 在调用 BTSORTSUPPORT 函数之前，ssup_extra 被置为零，之后
	 * 不再被调用者修改。
	 */
	void	   *ssup_extra;		/* 操作类函数的工作区 */

	/*
	 * 在调用 BTSORTSUPPORT 函数之前，函数指针被置为零，必须
	 * 由它设置以供其希望提供的加速方法。比较器指针必须被设置，
	 * 其他是可选的。
	 */

	/*
	 * 比较器函数的 API 与传统 btree 比较函数相同，即，返回 <0、0，
	 * 或 >0，具体取决于 x 小于、等于或大于 y。注意 x 和 y 保证
	 * 不为 NULL，并且也没有办法返回 NULL。
	 *
	 * 这可以是权威比较器，或者是简化比较器。核心代码可能会在
	 * 创建操作类支持函数的初始偏好之上切换，尽管最初指示
	 * 可以适用简化，通过重新分配权威比较器。
	 */
	int			(*comparator) (Datum x, Datum y, SortSupport ssup);

	/*
	 * “简化键”基础设施如下。
	 *
	 * 所有回调必须由使用此可选附加基础设施的排序支持操作类
	 * 设置（除非由于某种原因操作类未继续使用简化，这种情况下
	 * abbrev_converter 必须不设置）。
	 *
	 * 这允许操作类作者提供一个转换例程，用于创建基础类型的
	 * 替代表示（一个“简化键”）。这种表示必须是按值传递的，
	 * 通常将使用只有操作类知道的某种特定格式。也必须提供一个
	 * 替代比较器，仅用于此替代表示（分配给“comparator”）。
	 * 这种表示是原始 Datum 的简单近似。必须能够使用提供的
	 * 替代比较器相互比较这种表示的日期，任何非零返回值都应
	 * 可靠地表示适当比较的结果。从替代比较器返回零并不表示
	 * 相等，正如传统支持例程 1 所示，它表示不能确定
	 * 两个简化值的比较结果。因此，需要使用 “abbrev_full_comparator”/
	 * ApplySortAbbrevFullComparator() 进行适当比较。在许多情况下，
	 * 这导致大部分或所有的比较仅使用廉价的替代比较函数，
	 * 通常实现为编译为仅几条 CPU 指令的代码。CPU 缓存未命中的惩罚
	 * 很昂贵；为了获得良好的整体性能，排序基础设施必须在
	 * 缓存性能上进行大量权衡。
	 *
	 * 操作类作者在设计编码方案时必须考虑简化键的最终基数。
	 * 一种策略在某种使用模式下可能工作得比另一种策略更好，
	 * 而在另一种使用模式下可能正好相反。所有这些因素都必须考虑。
	 */

	/*
	 * “简化”关心是否原则上适用简化键优化（也就是说，
	 * 排序支持例程需要知道它是否在处理一个可以有用地
	 * 打包在一起的简化表示的键。通常，这是主属性键）。
	 * 但是，请注意，为了确定不适用简化，核心代码总是检查
	 * 操作类是否设置了 abbrev_converter。这是对操作类
	 * 的一次性消息。
	 */
	bool		abbreviate;

	/*
	 * 从原始表示转换为缩略格式的转换器。核心代码使用此回调将按引用传递的 "原始" Datum 转换为按值传递的缩略键 Datum。请注意，原始值被保证为非空，因为将 NULL 成分纳入临时成本模型是没有意义的。
	 *
	 * abbrev_converter 会被测试以确定是否正在使用缩略形式。核心代码可能将其设置为 NULL，以表示不应使用缩略格式（这与排序支持例程无关）。但是，当立即确定不应进行缩略时（例如，对于 !abbreviate 调用，或由于平台特有的使用缩略格式的障碍），排序支持例程不得设置它。
	 */
	Datum		(*abbrev_converter) (Datum original, SortSupport ssup);

	/*
	 * abbrev_abort 回调允许客户端验证当前策略是否有效，使用自定义成本模型的排序支持例程。如果在实际中有很多重复的缩略键，能够在转换成本过高之前放弃策略是有用的（也许某些特定于操作类的调整也是有用的）。
	 */
	bool		(*abbrev_abort) (int memtupcount, SortSupport ssup);

	/*
	 * 用于生成缩略表示的键的完整、权威比较器，当缩略比较无结论时（通过调用 ApplySortAbbrevFullComparator()），或在核心系统最终决定不使用缩略时用于替换 "comparator"。
	 */
	int			(*abbrev_full_comparator) (Datum x, Datum y, SortSupport ssup);
} SortSupportData;


/*
 * 应用排序比较器函数并返回三向比较结果。此函数妥善处理反向排序和 NULL 排序。
 */
static inline int
ApplySortComparator(Datum datum1, bool isNull1,
					Datum datum2, bool isNull2,
					SortSupport ssup)
{
	int			compare;

	if (isNull1)
	{
		if (isNull2)
			compare = 0;		/* NULL "=" NULL */
		else if (ssup->ssup_nulls_first)
			compare = -1;		/* NULL "<" NOT_NULL */
		else
			compare = 1;		/* NULL ">" NOT_NULL */
	}
	else if (isNull2)
	{
		if (ssup->ssup_nulls_first)
			compare = 1;		/* NOT_NULL ">" NULL */
		else
			compare = -1;		/* NOT_NULL "<" NULL */
	}
	else
	{
		compare = ssup->comparator(datum1, datum2, ssup);
		if (ssup->ssup_reverse)
			INVERT_COMPARE_RESULT(compare);
	}

	return compare;
}

static inline int
ApplyUnsignedSortComparator(Datum datum1, bool isNull1,
							Datum datum2, bool isNull2,
							SortSupport ssup)
{
	int			compare;

	if (isNull1)
	{
		if (isNull2)
			compare = 0;		/* NULL "=" NULL */
		else if (ssup->ssup_nulls_first)
			compare = -1;		/* NULL "<" NOT_NULL */
		else
			compare = 1;		/* NULL ">" NOT_NULL */
	}
	else if (isNull2)
	{
		if (ssup->ssup_nulls_first)
			compare = 1;		/* NOT_NULL ">" NULL */
		else
			compare = -1;		/* NOT_NULL "<" NULL */
	}
	else
	{
		compare = datum1 < datum2 ? -1 : datum1 > datum2 ? 1 : 0;
		if (ssup->ssup_reverse)
			INVERT_COMPARE_RESULT(compare);
	}

	return compare;
}

#if SIZEOF_DATUM >= 8
static inline int
ApplySignedSortComparator(Datum datum1, bool isNull1,
						  Datum datum2, bool isNull2,
						  SortSupport ssup)
{
	int			compare;

	if (isNull1)
	{
		if (isNull2)
			compare = 0;		/* NULL "=" NULL */
		else if (ssup->ssup_nulls_first)
			compare = -1;		/* NULL "<" NOT_NULL */
		else
			compare = 1;		/* NULL ">" NOT_NULL */
	}
	else if (isNull2)
	{
		if (ssup->ssup_nulls_first)
			compare = 1;		/* NOT_NULL ">" NULL */
		else
			compare = -1;		/* NOT_NULL "<" NULL */
	}
	else
	{
		compare = DatumGetInt64(datum1) < DatumGetInt64(datum2) ? -1 :
			DatumGetInt64(datum1) > DatumGetInt64(datum2) ? 1 : 0;
		if (ssup->ssup_reverse)
			INVERT_COMPARE_RESULT(compare);
	}

	return compare;
}
#endif

static inline int
ApplyInt32SortComparator(Datum datum1, bool isNull1,
						 Datum datum2, bool isNull2,
						 SortSupport ssup)
{
	int			compare;

	if (isNull1)
	{
		if (isNull2)
			compare = 0;		/* NULL "=" NULL */
		else if (ssup->ssup_nulls_first)
			compare = -1;		/* NULL "<" NOT_NULL */
		else
			compare = 1;		/* NULL ">" NOT_NULL */
	}
	else if (isNull2)
	{
		if (ssup->ssup_nulls_first)
			compare = 1;		/* NOT_NULL ">" NULL */
		else
			compare = -1;		/* NOT_NULL "<" NULL */
	}
	else
	{
		compare = DatumGetInt32(datum1) < DatumGetInt32(datum2) ? -1 :
			DatumGetInt32(datum1) > DatumGetInt32(datum2) ? 1 : 0;
		if (ssup->ssup_reverse)
			INVERT_COMPARE_RESULT(compare);
	}

	return compare;
}

/*
 * 应用排序比较器函数并使用完整、权威比较器返回三向比较结果。此函数妥善处理反向排序和 NULL 排序。
 */
static inline int
ApplySortAbbrevFullComparator(Datum datum1, bool isNull1,
							  Datum datum2, bool isNull2,
							  SortSupport ssup)
{
	int			compare;

	if (isNull1)
	{
		if (isNull2)
			compare = 0;		/* NULL "=" NULL */
		else if (ssup->ssup_nulls_first)
			compare = -1;		/* NULL "<" NOT_NULL */
		else
			compare = 1;		/* NULL ">" NOT_NULL */
	}
	else if (isNull2)
	{
		if (ssup->ssup_nulls_first)
			compare = 1;		/* NOT_NULL ">" NULL */
		else
			compare = -1;		/* NOT_NULL "<" NULL */
	}
	else
	{
		compare = ssup->abbrev_full_comparator(datum1, datum2, ssup);
		if (ssup->ssup_reverse)
			INVERT_COMPARE_RESULT(compare);
	}

	return compare;
}

/*
 * 我们为此特殊化了排序例程的 Datum 比较函数。安装这些作为其比较器或缩略比较器的数据类型有资格获得更快的排序。
 */
extern int	ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup);
#if SIZEOF_DATUM >= 8
extern int	ssup_datum_signed_cmp(Datum x, Datum y, SortSupport ssup);
#endif
extern int	ssup_datum_int32_cmp(Datum x, Datum y, SortSupport ssup);

/* utils/sort/sortsupport.c 中的其他函数 */
extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);
extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);
extern void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy,
										   SortSupport ssup);
extern void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup);

#endif							/* SORTSUPPORT_H */
